/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v1;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:HeapSort.java v1.0 2018/8/11 上午10:56 LvJing Exp $
 */
public class HeapSort {

    public int[] heapSort(int[] arr) {
        if (arr == null || arr.length <= 1)
            return arr;

        // 堆排序思路为，第一次对整个数组构建最大堆，堆顶就是最大元素，放入最后，第二次排序最后一个元素，构建最大堆，堆顶最大元素放入倒数第二个位置。。。
        for (int i = 0; i < arr.length - 1; i++) {
            buildMaxHeap(arr, arr.length - 1 - i);
            swap(arr, 0, arr.length - 1 -i);
        }
        return arr;
    }

    public int[] heapSort2(int[] arr) {
        if (arr == null || arr.length <= 1)
            return arr;

        for (int i = 0; i < arr.length - 1; i++) {
            buildMinHeap(arr, arr.length - 1 - i);
            swap(arr, 0, arr.length - 1 - i);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int lastPos) {
        for (int i = (lastPos - 1) / 2; i >= 0; i--) {
            int k = i;
            while (k*2 + 1 <= lastPos) {
                int biggerPos = k*2 + 1;
                if (biggerPos < lastPos) {
                    if (arr[biggerPos] < arr[biggerPos + 1])
                        biggerPos++;
                }
                if (arr[k] < arr[biggerPos]) {
                    swap(arr, k, biggerPos);
                    k = biggerPos;
                } else {
                    break;
                }
            }
        }
    }

    private void buildMinHeap(int[] arr, int lastPos) {
        for (int i = (lastPos-1)/2; i >= 0; i--) {
            int k = i;
            while (k*2 + 1 <= lastPos) {
                int smallerPos = k*2 + 1;
                if (smallerPos < lastPos) {
                    if (arr[smallerPos] > arr[smallerPos + 1])
                        smallerPos++;
                }
                if (arr[k] > arr[smallerPos]) {
                    swap(arr, k, smallerPos);
                    k = smallerPos;
                } else {
                    break;
                }
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        heapSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
